
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>Peterson算法实现spin lock - Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="本文详细分析了针对两个线程的peterson算法，用于实现spin lock。">
  <meta name="keywords" content="并行编程 并发编程 peterson peterson算法 spin lock">

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/blog/2016/03/04/petersonalgorithm/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">Peterson算法实现spin lock</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-03-04T22:26:51+08:00'><span class='date'><span class='date-month'>Mar</span> <span class='date-day'>4</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:26 pm</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><p>对spin lock和mutex不熟悉的朋友，可以看<a href="http://www.yebangyu.org/blog/2016/01/24/spinlock-and-mutex/">上篇</a>博客。</p>

<h2 id="section">提出问题</h2>

<p>如何仅仅通过load和store实现spin lock呢？</p>

<p>本文只考虑、只针对只有两个线程的情形。假设这两个线程的id分别为0和1。编程环境为X86体系结构 + Intel CPU + gcc</p>

<!--more-->

<h2 id="section-1">分析问题</h2>

<h3 id="section-2">尝试一：仅使用一个变量</h3>

<p>仅使用一个bool类型变量flag，线程i申请锁时，查看flag是否为1-i，如果不是，说明另外一个线程没有在临界区，申请成功，并把flag的值设置为i。</p>

<p>这种方法的问题在于，检查flag是否为1-i，以及设置flag为i这两步不是原子的，无法仅仅通过load和store来原子实现。（需要CAS等类似的原子操作）</p>

<h3 id="section-3">尝试二：使用两个变量</h3>

<p>根据前面的分析，我们可以使用两个bool变量flag[0]和flag[1]。线程i申请锁时，先把flag[i]设置为true，表示自己试图进入临界区，然后查看flag[1-i]是否为true，如果是，说明另一个线程在临界区，于是spin。</p>

<p>这个方法的问题在于可能发生这样的问题：</p>

<p>线程0把flag[0]设置为true，这时候还没开始检查flag[1]，此时线程1把flag[1]设置为true。</p>

<p>接下去，每个线程都发现对方的flag为true，而实际上两个都没在临界区中，却谁都没法拿到锁，发生starvation现象。</p>

<h3 id="section-4">尝试三：使用三个变量</h3>

<p>在尝试二的基础上，再增加一个变量turn，表示谁先将自己的flag设置为true（仅仅通过那两个flag是没法区分的，想想看，是不是这样的）。因此这个变量可以用来裁决谁取得进入临界区的权利。</p>

<h2 id="section-5">解决问题</h2>

<p>以上尝试三所描述的方法，就是大名鼎鼎的peterson算法的雏形了。简单实现如下（注意，本文的平台是x86体系结构 + Intel CPU + gcc）：</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
<span class="line-number">16</span>
<span class="line-number">17</span>
<span class="line-number">18</span>
<span class="line-number">19</span>
<span class="line-number">20</span>
<span class="line-number">21</span>
<span class="line-number">22</span>
<span class="line-number">23</span>
<span class="line-number">24</span>
<span class="line-number">25</span>
<span class="line-number">26</span>
<span class="line-number">27</span>
<span class="line-number">28</span>
<span class="line-number">29</span>
<span class="line-number">30</span>
<span class="line-number">31</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="k">class</span> <span class="nc">PetersonSpinLock</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="k">public</span><span class="o">:</span>
</span><span class="line">    <span class="n">PetersonSpinLock</span><span class="p">()</span>
</span><span class="line">    <span class="p">{</span>
</span><span class="line">      <span class="n">flags_</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span>
</span><span class="line">      <span class="n">flags_</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span>
</span><span class="line">      <span class="n">turn_</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span><span class="c1">//initial value does not matter</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">    <span class="kt">bool</span> <span class="n">lock</span><span class="p">(</span><span class="kt">int</span> <span class="n">thread_id</span><span class="p">)</span>
</span><span class="line">    <span class="p">{</span>
</span><span class="line">      <span class="kt">int</span> <span class="n">other</span> <span class="o">=</span> <span class="o">!</span><span class="n">thread_id</span><span class="p">;</span>
</span><span class="line">      <span class="n">flags_</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
</span><span class="line">      <span class="n">COMPILER_BARRIER</span><span class="p">();</span>
</span><span class="line">      <span class="n">turn_</span> <span class="o">=</span> <span class="n">thread_id</span><span class="p">;</span>
</span><span class="line">      <span class="n">CPU_BARRIER</span><span class="p">();</span><span class="c1">// essential</span>
</span><span class="line">      <span class="k">while</span><span class="p">(</span><span class="n">flags_</span><span class="p">[</span><span class="n">other</span><span class="p">]</span> <span class="o">&amp;&amp;</span> <span class="n">turn_</span> <span class="o">==</span> <span class="n">thread_id</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">        <span class="n">CPU_RELAX</span><span class="p">();</span><span class="c1">//spin</span>
</span><span class="line">      <span class="p">}</span>
</span><span class="line">      <span class="c1">//get lock successfully</span>
</span><span class="line">      <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">    <span class="kt">bool</span> <span class="n">unlock</span><span class="p">(</span><span class="kt">int</span> <span class="n">thread_id</span><span class="p">)</span>
</span><span class="line">    <span class="p">{</span>
</span><span class="line">      <span class="n">flags_</span><span class="p">[</span><span class="n">thread_id</span><span class="p">]</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span>
</span><span class="line">      <span class="k">return</span> <span class="nb">true</span><span class="p">;</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">  <span class="k">private</span><span class="o">:</span>
</span><span class="line">    <span class="k">volatile</span> <span class="kt">bool</span> <span class="n">flags_</span><span class="p">[</span><span class="mi">2</span><span class="p">];</span>
</span><span class="line">    <span class="k">volatile</span> <span class="kt">bool</span> <span class="n">turn_</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

<p>以下是对peterson算法的思考和讨论。在看我的分析之前，请自己尝试思考以下问题：（温馨提示：在C/C++中，if条件判断是短路求值的。也就是说对于if(A &amp;&amp; B)，一旦知道A是false，那么B将不用evaluate了）</p>

<blockquote>
  <ul>
    <li>peterson算法如何防止starvation的发生？</li>
  </ul>
</blockquote>

<blockquote>
  <ul>
    <li>peterson算法如何防止两个线程同时进入临界区？</li>
  </ul>
</blockquote>

<blockquote>
  <ul>
    <li>代码13行和15行能否调换执行顺序？</li>
  </ul>
</blockquote>

<blockquote>
  <ul>
    <li>代码15行能否改为<code>turn_ = !thread_id</code> ？</li>
  </ul>
</blockquote>

<blockquote>
  <ul>
    <li>16行的cpu 级别的memory barrier是否必要？</li>
  </ul>
</blockquote>

<blockquote>
  <ul>
    <li>实现（针对两个线程的）peterson算法所需最少空间为多少？</li>
  </ul>
</blockquote>

<p>思考了没？下面我们来分析讨论一下：</p>

<h3 id="petersonstarvation">peterson算法如何防止starvation的发生？</h3>

<p>假设某时刻两个线程都在spin，也就是17行中while的条件对两个线程都成立，也就是说：</p>

<p>flag_[0] == true 并且 trun_ == 0 并且 flag_[1] == true 并且turn_ == 1</p>

<p>但是turn_只能有一个值，矛盾。</p>

<h3 id="peterson">peterson算法如何防止两个线程同时进入临界区？</h3>

<p>如果两者同时进入临界区，说明17行中的while判断对两个线程都为false，也就是说</p>

<p>flag_[1] == false 或者 turn _ == 1</p>

<p>同时</p>

<p>flag_[0] == false 或者 turn_ == 0</p>

<p>因此只有四种情形：</p>

<p>flag_[1] == false  &amp;&amp; flag_[0] == false  与13行矛盾</p>

<p>flag_[1] == false  &amp;&amp; turn_ == 0  与13行矛盾</p>

<p>turn_ == 1 &amp;&amp; flag_[0] == false 与13行矛盾</p>

<p>turn _ == 1 &amp;&amp; turn _ == 0 不可能发生</p>

<p>而一旦例如说，线程0，进入临界区后，线程1会因为turn_的值而spin，直到线程0通过unlock将flag_[0]设置为false。</p>

<p>因此，13、15两行的顺序很重要。是这样的吗？接着往下看。</p>

<h3 id="section-6">代码13行和15行能否调换执行顺序？</h3>

<p>不可以，否则可能发生两个线程同时进入临界区。</p>

<p>考虑以下情形：</p>

<p>线程0执行turn_ = 0</p>

<p>线程1执行turn_ = 1</p>

<p>线程1执行flag_[1] = true</p>

<p>线程1执行17行的判断，因为flag_[0]为false，所以线程1进入临界区。</p>

<p>线程0执行flag_[0] = true</p>

<p>线程0执行17行判断，此时turn_等于1，所以线程0也进入临界区。</p>

<p>因此13行和15行执行顺序不可以交换；而这两个都是store操作，在X86 Intel CPU下，cpu不会乱序执行它们，因此只需要在14行增加一个compiler级别的memory barrier，防止编译器乱序即可。</p>

<h3 id="turn--threadid">代码15行能否改为<code>turn_ = !thread_id</code></h3>

<p>可以。只是如果15行改为<code>turn_ = !thread_id</code>，那么17行需要将<code>turn_ == thread_id</code>也改为<code>turn_ == !thread_id</code>。也就是说turn_的初始值是什么并不重要，turn_设置成什么值也不太重要，重要的是通过turn_能区分出谁先尝试申请锁。</p>

<h3 id="cpu-memory-barrier">16行的cpu 级别的Memory Barrier是否必要？</h3>

<p>非常必要。否则17行对flags_[other]的读取（判断）操作可能和15行发生乱序（写读乱序。而13、15属于写写，是不会被CPU乱序执行的，不用加cpu 级别的memory barrier），最后可能导致两个线程同时进入临界区。这点，请读者务必自己亲自分析。非常重要！</p>

<p>不加Memory Barrier，乱序后，考虑以下情形：</p>

<p>线程0判断flag_[1]，发现为false（此时线程1还没开始调用lock函数，flag_[1]还是它的初始值false），进入临界区。</p>

<p>线程1判断flag_[0]，发现为true</p>

<p>线程1执行<code>turn_ = 1</code></p>

<p>线程0执行<code>turn_ = 0</code></p>

<p>线程1执行17行判断，此时turn_等于0，所以线程1也进入临界区。</p>

<h3 id="peterson-1">实现（针对两个线程的）peterson算法所需最少空间为多少？</h3>

<p>3个bit足矣。两个flag_两个bit，turn_也只需要1个bit。</p>

<h2 id="section-7">附录：</h2>

<p>在X86下，<code>CPU_BARRIER</code>和<code>CPU_RELAX</code>以及<code>COMPILER_BARRIER</code>可以用gcc内置feature，通过宏来实现：</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="cp">#define CPU_BARRIER() __sync_synchronize()</span>
</span><span class="line"><span class="cp">#define COMPILER_BARRIER() __asm__ __volatile__(&quot;&quot; : : : &quot;memory&quot;)</span>
</span><span class="line"><span class="cp">#define CPU_RELAX() __asm__ __volatile__(&quot;pause&quot;: : :&quot;memory&quot;)</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

<p>18行不用CPU_RELAX而是简单的一个分号行吗？可以的。不过加了CPU_RELAX可以提高性能、节能减排。</p>

<h2 id="section-8">致谢</h2>

<p>本文发出后，微博网友@finalpatch 指出应在代码的29、30行加上volatile。非常感谢。</p>

<p>本文发出后，微博网友@linyvxiang 指出了文中的两处笔误。非常感谢。</p>
</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Yebangyu</span></span>

      




<time class='entry-date' datetime='2016-03-04T22:26:51+08:00'><span class='date'><span class='date-month'>Mar</span> <span class='date-day'>4</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:26 pm</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/bing-xing-bian-cheng/'>并行编程</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  
  
</div>

    
    <p class="meta">
      
        <a class="basic-alignment left" href="/blog/2016/02/24/writeelegantcodes/" title="Previous Post: 编写高质量代码(下)">&laquo; 编写高质量代码(下)</a>
      
      
        <a class="basic-alignment right" href="/blog/2016/03/09/quicksort/" title="Next Post: 深入解析快速排序(Quick Sort)">深入解析快速排序(Quick Sort) &raquo;</a>
      
    </p>
  </footer>
</article>


</div>

<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
